package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/find-the-losers-of-the-circular-game/'>找出转圈游戏输家(Find the Losers of the Circular Game)</a>
 * <p>n 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 1 到 n 编号。准确的说，从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i + 1) 个朋友的位置（1 <= i < n），而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。</p>
 * <p>游戏规则如下：</p>
 * <p>
 * 第 1 个朋友接球。
 *     <ul>
 *         <li>接着，第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。</li>
 *         <li>然后，接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。</li>
 *         <li>接着，接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友，以此类推。</li>
 *     </ul>
 *     换句话说，在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。
 * </p>
 * <p>当某个朋友第 2 次接到球时，游戏结束。</p>
 * <p>在整场游戏中没有接到过球的朋友是 输家 。</p>
 * <p>给你参与游戏的朋友数量 n 和一个整数 k ，请按升序排列返回包含所有输家编号的数组 answer 作为答案。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：n = 5, k = 2
 *      输出：[4,5]
 *      解释：以下为游戏进行情况：
 *          1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
 *          2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
 *          3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
 *          4）第 3 个朋友接到两次球，游戏结束。
 *
 * 示例 2：
 *      输入：n = 4, k = 4
 *      输出：[2,3,4]
 *          解释：以下为游戏进行情况：
 *          1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。
 *          2）第 1 个朋友接到两次球，游戏结束。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= k <= n <= 50</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 13:36
 */
public class LC2682FindTheLosersOfTheCircularGame_S {

    static class Solution {
        public int[] circularGameLosers(int n, int k) {
            boolean[] flags = new boolean[n];
            int index = 0;
            int m = 1;
            int winCount = 0;
            while (!flags[index]) {
                flags[index] = true;
                index = (index + k * m++) % n;
                ++winCount;
            }
            int[] res = new int[n - winCount];
            int resIndex = 0;
            for (int i = 0; i < flags.length; i++) {
                if (!flags[i]) {
                    res[resIndex++] = i + 1;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.circularGameLosers(5, 2));
        Printer.printArrayInt(solution.circularGameLosers(4, 4));
    }
}
